package fun.coding.bfsdfs;

import java.util.LinkedList;
import java.util.Queue;

public class BFSImpl implements BFS {

    /*   
     *  let's say it is 3x3
     *  a b c 
     *  d e f
     *  g h i
     *  
     *   it starts at e, and can move to all the directions but not repeated. 
     *   print out all the words (could look up in a dictionary which uses trie[prefix tree])
     *   
        TODO: I need to make a tuple entry. and it didn't remember the last step 
     *   http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver
     * */
    @Override
    public void findWordsInMatrix(char[][] chars) {
        int row = chars.length;
        int col = chars[0].length;
        
        int startX = chars.length / 2;
        int startY = chars.length / 2;
        
        Queue<String> q = new LinkedList<String>();
        q.add(new Character(chars[startX][startY]).toString());
        
        while(!q.isEmpty()) {
            String cur = q.poll();
            System.out.println(cur);
            findValidNextHelper(q, startX, startY, cur, chars, row, col);
        }
    }

    private String findValidNext(int i, int j, char[][] chars, int row, int col) {
        if(!(i >= 0 && i < col && j >= 0 && j < row)) {
            System.out.println("i is " + i + "j is " + j);
            return new Character(chars[i][j]).toString();
        }
        return null;
    }
    
    private void findValidNextHelper(Queue<String> q, int startX, int startY, String cur, char[][] chars, int row, int col) {
     // There is 8 directions it can go.
        String c = findValidNext(startX - 1, startY - 1, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
        
        c = findValidNext(startX - 1, startY, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
        
        c = findValidNext(startX - 1, startY + 1, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
        
        c = findValidNext(startX, startY - 1, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
        
        c = findValidNext(startX, startY + 1, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
        
        c = findValidNext(startX + 1, startY - 1, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
        
        c = findValidNext(startX + 1, startY, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
        
        c = findValidNext(startX + 1, startY + 1, chars, row, col);
        if(c != null) {
            q.add(cur + "c");
        }
    }
    
}
